#define _CRT_SECURE_NO_WARNINGS 1


#include<map>
#include<vector>
#include<string>
#include<iostream>

using namespace std;

bool Func(map<string, int>& hash, map<string, int>& hash_words)
{
    auto it1 = hash.begin();
    auto it2 = hash_words.begin();
    while (it1 != hash.end())
    {
        if (it1->first != it2->first || it1->second != it2->second)
        {
            return false;
        }
        it1++;
        it2++;
    }
    return true;
}

vector<int> findSubstring(string s, vector<string>& words)
{
    int len = words[0].size(), size = s.size();
    map<string, int> hash_words;
    for (auto& e : words)
    {
        hash_words[e]++;
    }
    vector<int> v;
    int left = 0, right = 0, count = 0;
    for (int i = 0; i < len; i++)
    {
        map<string, int> hash;
        left = right = i;
        count = 0;
        while (right + len <= size)
        {
            string str(s.begin() + right, s.begin() + right + len);
            hash[str]++;
            count++;
            while (count == words.size())
            {
                if (Func(hash, hash_words))
                {
                    v.push_back(left);
                }
                string str2(s.begin() + left, s.begin() + left + len);
                hash[str2]--;
                if (hash[str2] == 0)
                {
                    hash.erase(str2);
                }
                left += len;
                count--;
            }
            right += len;
        }
    }
    return v;
}

int main()
{
    string s = "lingmindraboofooowingdingbarrwingmonkeypoundcake";
    vector<string> v = { "fooo","barr","wing","ding","wing" };
    vector<int> ret = findSubstring(s, v);
    for (auto& e : ret)
    {
        cout << e << ' ';
    }
    cout << endl;

	return 0;
}